Set membership matching is used in a number of different contexts to determine whether a given data item is included in a given set of data items. Set membership matching is used in a number of different functions, including, for example, data deduplication. For example, in data deduplication, a computing device may determine whether a data block is a duplicate of an existing data block at the computing device by performing set membership matching.